package com.ahpu.lyf.binarytree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "吴用");
        TreeNode node3 = new TreeNode(3, "卢俊义");
        TreeNode node4 = new TreeNode(4, "林冲");
        TreeNode node5 = new TreeNode(5, "李逵");
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        BinaryTree binaryTree = new BinaryTree(node1);
        System.out.println("前缀遍历~~~~~~~~~~~~~~~~~~~~~~~~~·");
        binaryTree.preOrder();
        System.out.println("中缀遍历~~~~~~~~~~~~~~~~~~~~~~~~~·");
        binaryTree.infixOrder();
        System.out.println("后缀遍历~~~~~~~~~~~~~~~~~~~~~~~~~·");
        binaryTree.suffixOrder();

        System.out.println("前缀遍历查找~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println(binaryTree.preOrderSerach(15));
        System.out.println(binaryTree.preOrderSerach(5));

        System.out.println("中缀遍历查找~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println(binaryTree.infixOrderSearch(15));
        System.out.println(binaryTree.infixOrderSearch(5));

        System.out.println("后缀遍历查找~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println(binaryTree.suffixOrderSearch(15));
        System.out.println(binaryTree.suffixOrderSearch(5));

        System.out.println("删除节点前~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        binaryTree.suffixOrder();
        binaryTree.delNode(3);
        System.out.println("删除节点后~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        binaryTree.suffixOrder();
    }
}

/**
 * 二叉树
 */
class BinaryTree {
    private TreeNode root;

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    /**
     * 前缀遍历
     */
    public void preOrder() {
        if (root != null)
            root.preOrder();
        else
            System.out.println("二叉树为空！");
    }

    /**
     * 中缀遍历
     */
    public void infixOrder() {
        if (root != null)
            root.infixOrder();
        else
            System.out.println("二叉树为空！");
    }

    /**
     * 后缀遍历
     */
    public void suffixOrder() {
        if (root != null)
            root.suffixOrder();
        else
            System.out.println("二叉树为空！");
    }


    /**
     * 前缀遍历查找
     * @param id 要查的id
     * @return 查找的结果
     */
    public TreeNode preOrderSerach(Integer id) {
        if (root == null) {
            System.out.println("空树！！！");
            return null;
        }
        return root.preOrderSearch(id);
    }

    /**
     * 中缀遍历查找
     * @param id 要查找的id
     * @return 查找的结果
     */
    public TreeNode infixOrderSearch(Integer id){
        if (root==null){
            System.out.println("空树！！！");
            return null;
        }

        return root.infixOrderSerach(id);
    }

    /**
     * 后缀遍历查找
     * @param id 要查找的id
     * @return 查找的结果
     */
    public TreeNode suffixOrderSearch(Integer id){
        if (root==null){
            System.out.println("空树！！！");
            return null;
        }

        return root.suffixOrderSearch(id);
    }


    /**
     * 删除节点的方法
     * @param id 要删除的节点的id
     */
    public void delNode(Integer id){
        //如果根节点就是要删除的节点直接删除整棵树
        if (root.getId().equals(id)){
            root=null;
            return;
        }
        root.delNode(id);
    }
}


/**
 * 树的节点类
 */
class TreeNode {
    private Integer id;
    private String name;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前缀遍历     根左右
     */
    public void preOrder() {
        //先打印根节点
        System.out.println(this);

        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.preOrder();
        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.preOrder();
    }

    /**
     * 中缀遍历     左中右
     */
    public void infixOrder() {
        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.infixOrder();
        //打印根节点
        System.out.println(this);

        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.infixOrder();
    }


    /**
     * 后缀遍历     左右中
     */
    public void suffixOrder() {
        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.suffixOrder();
        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.suffixOrder();
        //打印根节点
        System.out.println(this);
    }

    /**
     * 前缀遍历查找
     * @param id 要查找的id
     * @return 查找的结果
     */
    public TreeNode preOrderSearch(Integer id) {
        System.out.println("一次前缀查询");
        //先判断节点
        if (this.id.equals(id))
            return this;

        TreeNode resNode = null;
        //左子树不为空，递归左子树
        if (this.left != null)
            resNode = this.left.preOrderSearch(id);

        //左子树递归完了找到就返回
        if (resNode != null)
            return resNode;

        //没找到继续递归右子树
        if (this.right != null)
            resNode = this.right.preOrderSearch(id);
        return resNode;
    }

    /**
     * 中缀遍历查找
     *
     * @param id 要查找的id
     * @return 查找的结果
     */
    public TreeNode infixOrderSerach(Integer id) {
        TreeNode resNode = null;
        //左子树不为空，递归左子树
        if (this.left != null)
            resNode = this.left.infixOrderSerach(id);

        //左子树递归完了找到就返回
        if (resNode!=null)
            return resNode;

        System.out.println("一次中缀查询");
        //判断节点
        if (this.id.equals(id))
            return this;

        //节点不是，继续递归右子树
        if (this.right != null)
            resNode = this.right.infixOrderSerach(id);

        return resNode;

    }

    /**
     * 后缀遍历查找
     * @param id 要查找的id
     * @return 查找的结果
     */
    public TreeNode suffixOrderSearch(Integer id){
        TreeNode resNode=null;
        //左子树不为空，递归左子树
        if (this.left!=null)
            resNode=this.left.suffixOrderSearch(id);

        //左子树递归完了找到就返回
        if (resNode!=null)
            return resNode;

        //没找到继续递归右子树
        if (this.right!=null)
            resNode=this.right.suffixOrderSearch(id);

        //右子树递归结束没找到判断节点
        if (resNode!=null)
            return resNode;

        System.out.println("一次后缀查询");
        //判断节点
        if (this.id.equals(id))
            return this;

        return null;
    }

    /**
     * 删除节点的方法
     * 叶子节点直接删除
     * 根节点直接删除子树
     * @param id 要删除节点的id
     */
    public void delNode(Integer id){
        //左子树不为空且左子树根节点就是要删除的节点
        if (this.left!=null&& this.left.id.equals(id)){
            this.left=null;
            return;
        }
        //左子树不为空且左子树根节点就是要删除的节点
        if (this.right!=null&&this.right.id.equals(id)){
            this.right=null;
            return;
        }
        //左子树不为空且左子树根节点不是要删除的节点，递归左子树
        if (this.left!=null){
            this.left.delNode(id);
        }

        //右子树不为空且右子树根节点不是要删除的节点，递归右子树
        if (this.right!=null){
            this.right.delNode(id);
        }
    }
}
